/// @tags: TODO
#include <cstdio>
#include <iostream>

using namespace std;

namespace BlueQuantum {

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 40;
int n;

struct Tre {
  int lmax, rmax, setmax, sum;
};

struct SegmentTree {
  int cnt, root;
  int l[MAXN], r[MAXN], ls[MAXN], rs[MAXN];
  int maxl[MAXN], maxr[MAXN], maxset[MAXN];
  int a[MAXN], val[MAXN];  // val区间和

  void pushup(int cur) {
    val[cur] = val[ls[cur]] + val[rs[cur]];
    maxl[cur] = max(maxl[ls[cur]], maxl[rs[cur]] + val[ls[cur]]);
    maxr[cur] = max(maxr[rs[cur]], maxr[ls[cur]] + val[rs[cur]]);
    maxset[cur] =
        max(maxset[ls[cur]], max(maxl[rs[cur]] + maxr[ls[cur]], maxset[rs[cur]]));
  }
  void build(int L, int R, int &cur) {
    cur = ++cnt;
    l[cur] = L;
    r[cur] = R;
    if (L == R) {
      val[cur] = a[L];
      maxl[cur] = a[L];
      maxr[cur] = a[L];
      maxset[cur] = a[L];
      return;
    }
    int mid = (L + R) >> 1;
    build(L, mid, ls[cur]);
    build(mid + 1, R, rs[cur]);
    pushup(cur);
    return;
  }
  Tre query(int cur, int L, int R) {
    Tre res;
    if (R >= r[cur] && L <= l[cur]) {
      res.lmax = maxl[cur];
      res.rmax = maxr[cur];
      res.setmax = maxset[cur];
      res.sum = val[cur];
      return res;
    }
    int mid = (l[cur] + r[cur]) >> 1;
    if (R <= mid) { return query(ls[cur], L, R); }
    if (L > mid) { return query(rs[cur], L, R); }
    Tre ltree = query(ls[cur], L, R);
    Tre rtree = query(rs[cur], L, R);
    res.lmax = max(ltree.lmax, rtree.lmax + ltree.sum);
    res.rmax = max(rtree.rmax, rtree.sum + ltree.rmax);
    res.setmax = max(ltree.rmax + rtree.lmax, max(ltree.setmax, rtree.setmax));
    res.sum = ltree.sum + rtree.sum;
    return res;
  }
  void modify(int value, int cur, int index) {
    if (l[cur] == r[cur]) {
      val[cur] = maxl[cur] = maxr[cur] = maxset[cur] = value;
      return;
    }
    int mid = (l[cur] + r[cur]) >> 1;
    if (index <= mid) modify(value, ls[cur], index);
    if (index > mid) modify(value, rs[cur], index);
    pushup(cur);
    return;
  }
} sgt;

int m, type;

int main() {
  cin >> n >> a >> b >> s;
  for (int i = 1; i <= n; ++i) { cin >> sgt.a[i]; }
  sgt.build(1, n, sgt.root);
  cin >> m;
  int a, b;
  for (int i = 1; i <= m; ++i) {
    cin >> type;
    if (type == 0) {
      cin >> a >> b;
      sgt.modify(b, 1, a);
    } else {
      cin >> a >> b;
      int ans = sgt.query(1, a, b).setmax;
      cout << ans << endl;
    }
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("「StOI-3」魔法.in", "r", stdin);
  freopen("「StOI-3」魔法.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
